
##编写斐波那契数列的函数并调⽤
# def fib(n):##n是形参
#  a,b =1,1
#  while a<n:
#     print(a,end=' ')
#     a,b=b,a+b
#     print(a,b)
# fib(1000)


# 使⽤递归法对整数进⾏因数分解
# import random
#
#
# def factors(num, fac=None):
#     if fac is None:
#         fac = []
#     # 处理边界情况：1不是质数
#     if num == 1:
#         return fac
#
#     # 检查是否质数
#     is_prime = True
#     # 只需检查到平方根范围
#     for i in range(2, int(num ** 0.5) + 1):
#         if num % i == 0:
#             is_prime = False
#             fac.append(i)
#             # 递归分解商
#             factors(num // i, fac)
#             break
#
#     # 如果是质数，添加自身
#     if is_prime:
#         fac.append(num)
#
#     return fac
#
#
# n = random.randint(2, 10 ** 8)
# facs = factors(n)
# result = '*'.join(map(str, facs))
# if n == eval(result):
#     print(n, '=', result)


# 编写并使⽤能够⽣成斐波那契数列的⽣成器函数

# def liu(x):
#     a,b=0,1
#     while a<x:
#         print(a,end=' ')
#         a,b=b,a+b
#         print(a,b)
#     return (a,b)
#
# c=int(input('请输入数字生成斐波那契数列'))
# liu(c)

# 接收字符串参数，返回⼀个元组，其中第⼀个元素为⼤写字⺟个数，第⼆个元素为⼩写
# 字⺟个数
# def liu(s):
#     big_num=0
#     sma_num=0
#     for i in s:
#         if i.isupper():
#             big_num+=1
#         if i.islower():
#             sma_num+=1
#     tup=(big_num,sma_num)
#     return tup
#
# s='sadaWQE'
# res=liu(s)
# print(res)


# 编写函数，接收⼀个整数t为参数，打印杨辉三⻆前t⾏
# def yanghui(t):
#     list=[1]
#
#     for i in range(t):
#         print(list)
#         list.append(0)
#         new_list=[]
#         for k in range(i+2):
#             if k==0 or k==i+1:
#                 new_list.append(1)
#             else:
#                 new_list.append(list[k]+list[k-1])
#         list.clear()
#         for g in new_list:
#             list.append(g)
#
#
#
#
#
# t=int(input('请输入打印多少行'))
# yanghui(t)



# 编写函数，接收⼀个正偶数为参数，输出两个素数，并且这两个素数之和等于原来的正偶数。如
# 果存在多组符合条件的素数，则全部输出。
# def is_prime(x):
#     if x < 2:
#         return False
#     for i in range(2, int(x ** 0.5) + 1):
#         if x % i == 0:
#             return False
#     return True
#
# def liu(n):
#     if n <= 2 or n % 2 == 1:
#         print('请输入正偶数')
#         return
#
#     result = []
#     for a in range(2, int(n * 0.5) + 1):
#         b = n - a
#         if is_prime(a) and is_prime(b):
#             result.append([a, b])
#
#     if result:
#         for pair in result:
#             print(f"{pair[0]} + {pair[1]} = {n}")
#     else:
#         print("没有找到符合条件的素数对。")
#
# n = int(input('输入一个正整数'))
# liu(n)



# 编写函数，计算字符串匹配的准确率。以打字练习程序为例，假设origin为原始内容，
# userInput为⽤⼾输⼊的内容，下⾯的代码⽤来测试⽤⼾输⼊的准确率。
# def liu(origin ,userIput):
#     a=0
#     b=0
#     list=[]
#     userlist=[]
#     for i in origin:
#        a+=1
#        list.append(i)
#     for u in userIput:
#        b+=1
#        userlist.append(u)
#     if a!=b:
#         return False
#     if a==b:
#         for o in range(a):
#             if list[o]==userlist[o]:
#                 return True
#             else:
#                 return False
#
#
# origin='hallo,word'
# userIput=input('请输入文本')
# res=liu(origin,userIput)
# if res:
#     print('准确')
# else:
#     print('不准确')

# 编写函数模拟猜数游戏。系统随机产⽣⼀个数，玩家最多可以猜5次，系统会根据玩家的猜测进
# ⾏提⽰，玩家则可以根据系统的提⽰对下⼀次的猜测进⾏适当调整。
# import random
# def liu():
#     i=5
#     b=random.randint(0,100)
#     while i>0:
#         a=int(input('请输入'))
#         if a>b:
#             i-=1
#             print('大了')
#         if a==b:
#             print('对了')
#         if a<b:
#             i-=1
#             print('小了')
#     print('机会用尽，正确答案为',b)
#
# liu()

# 编写函数模拟报数游戏。有n个⼈围成⼀圈，顺序编号，从第⼀个⼈开始从1到k（假设k=3）报
# 数，报到k的⼈退出圈⼦，然后圈⼦缩⼩，从下⼀个⼈继续游戏，问最后留下的是原来的第⼏
# 号。

# def liu(n,k):
#     a=0
#     list=[]
#     for i in range(n):
#         list.append(i)
#     while n>1:
#        for p in range(n):
#            o=0
#            a+=1
#            o+=1
#            if a%k==0:
#               del list[o-1]
#               o-=1
#               n-=1
#     return (list)
#
# n=int(input('输入多少人'))
# k=int(input('输入k值'))
# res=liu(n,k)
# print(res)



#汉诺塔问题基于递归算法的实现。
# 据说古代有⼀个梵塔，塔内有三个底座A、B、C，A座上有64个盘⼦，盘⼦⼤⼩不等，⼤的在下，⼩
# 的在上。有⼀个和尚想把这64个盘⼦从A座移到C座，但每次只能允许移动⼀个盘⼦，在移动盘⼦的
# 过程中可以利⽤B座，但任何时刻3个座上的盘⼦都必须始终保持⼤盘在下、⼩盘在上的顺序。如果
# 只有⼀个盘⼦，则不需要利⽤B座，直接将盘⼦从A移动到C即可。和尚想知道这项任务的详细移动步
# 骤和顺序。这实际上是⼀个⾮常巨⼤的⼯程，是⼀个不可能完成的任务。根据数学知识我们可以知
# 道，移动n个盘⼦需要2^n-1步，64个盘⼦需要18446744073709551615步。如果每步需要⼀秒钟的
# 话，那么就需要584942417355.072年。
# move=[]
# def liu(n,A,B,C):
#       if n==1:
#         move.append(f"{A}==>{C}")
#       else:
#         liu(n-1,A,C,B)
#         move.append(f"{A}==>{C}")
#         liu(n-1,B,A,C)
#
#       return move
#
# n=int(input('请输入多少盘子'))
# A='A'
# B='B'
# C='C'
# res=liu(n,A,B,C)
# print(res)

# 编写函数计算任意位数的⿊洞数。⿊洞数是指这样的整数：由这个数字每位上的数字组成的最
# ⼤数减去每位数字组成的最⼩数仍然得到这个数⾃⾝。例如3位⿊洞数是495，因为954-459=495，4
# 位数字是6174，因为7641-1467=6174

# def liu(n):
#     start=10**(n-1)
#     end=10**n
#     for i in range(start,end,1):
#         big=''.join(sorted(str(i),reverse=True))
#         small=''.join(reversed(big))
#         big, small= map(int,(big, small))
#         if big-small==i:
#             print(i)
#
# n=int(input('输入位数'))
# liu(n)


# 编写函数，使⽤算法实现冒泡排序算法
# def liu(n,list):
#     if n==0:
#         return list
#     b=0
#     for i in list:
#        b+=1
#     for a in range(b-1):
#         if list[a]>list[a+1]:
#             p=list[a]
#             list[a]=list[a+1]
#             list[a+1]=p
#     liu(n-1,list)
#     return list
#
# n=int(input('请输入进行几次冒泡排序'))
# i=0
# list=[]
# while i<n+2:
#    c=int(input('请输入序列'))
#    list.append(c)
#    i+=1
# res=liu(n,list)
# print(res)

# 编写函数，模拟选择法排序
# def selection_sort(arr, reverse=False):
#     """
#     选择排序实现
#
#     参数:
#         arr (list): 待排序的列表
#         reverse (bool): 是否降序排序，默认False（升序）
#
#     返回:
#         list: 排序后的列表
#     """
#     n = len(arr)
#
#     # 遍历所有数组元素
#     for i in range(n):
#         # 找到未排序部分中最小或最大元素的索引
#         target_index = i
#
#         for j in range(i + 1, n):
#             # 根据reverse参数决定比较方式
#             if reverse:
#                 if arr[j] > arr[target_index]:
#                     target_index = j
#             else:
#                 if arr[j] < arr[target_index]:
#                     target_index = j
#
#         # 将找到的最小/大元素与当前位置元素交换
#         arr[i], arr[target_index] = arr[target_index], arr[i]
#
#     return arr
#
#
# # 测试代码
# if __name__ == "__main__":
#     # 测试数据
#     test_cases = [
#         [64, 25, 12, 22, 11],
#         [5, 4, 3, 2, 1],
#         [1, 2, 3, 4, 5],
#         [3, 1, 4, 1, 5, 9, 2, 6],
#         []
#     ]
#
#     for data in test_cases:
#         print(f"原始数组: {data}")
#
#         # 升序排序
#         sorted_asc = selection_sort(data.copy())
#         print(f"升序排序: {sorted_asc}")
#
#         # 降序排序
#         sorted_desc = selection_sort(data.copy(), reverse=True)
#         print(f"降序排序: {sorted_desc}")
#         print("-" * 40)

# 编写函数，模拟⼆分法查找
# def liu(list,n):
#     start =0
#     end=len(list)
#     while start<end:
#         m = (start + end) / 2
#         if n == m:
#             return m
#         if n < m:
#             end = m - 1
#         if n > m:
#             start = m + 1
#     return m

# 编写函数，查找给定序列的最⻓递增⼦序列。
# def lengthOfLIS_dp(nums):
#     """
#     动态规划解法：时间复杂度 O(n²)，空间复杂度 O(n)
#     """
#     if not nums:
#         return 0
#
#     n = len(nums)
#     # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
#     dp = [1] * n
#
#     for i in range(1, n):
#         for j in range(i):
#             if nums[i] > nums[j]:
#                 dp[i] = max(dp[i], dp[j] + 1)
#
#     return max(dp)